#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stack>
#include<unordered_map>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[i - 1] == '*') dp[0][i] = true;
            else break;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else {
                    dp[i][j] = (p[j - 1] == '?' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];
                }

            }
        }
        return dp[m][n];
    }

    int numDistinct(string s, string t) {
        int m = t.size(), n = s.size();
        vector<vector<double>> dp(m + 1, vector<double>(n + 1));
        for (int i = 0; i <= n; ++i) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = s[j - 1] == t[i - 1] ? dp[i - 1][j - 1] : 0;
                dp[i][j] += dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    vector<vector<int>> f;
    vector<vector<string>> ret;
    string path;
    vector<string> ans;
    int n;
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(ans);
            return;
        }
        for (int j = i; j < n; ++j) {
            if (isPalindrome(s, i, j) == 1) {
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }

    int isPalindrome(const string& s, int i, int j) {
        if (f[i][j]) return f[i][j];
        if (s[i] == s[j]) {
            return f[i][j] = i + 1 < j ? isPalindrome(s, i + 1, j - 1) : 1;
        }
        else {
            return f[i][j] = -1;
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n));
        dfs(s, 0);
        return ret;
    }

    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums2.size();
        stack<int> st;
        unordered_map<int, int> hash;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && st.top() < nums2[i]) {
                hash[st.top()] = nums2[i];
                st.pop();
            }
            st.emplace(nums2[i]);
        }
        for (int num : nums1) {
            if (hash.count(num))
                ans.push_back(hash[num]);
            else ans.push_back(-1);
        }
        return ans;
    }

    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        stack<int> st;
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && prices[i] <= prices[st.top()]) {
                int pre = st.top();
                ans[pre] = prices[pre] - prices[i];
                st.pop();
            }
            st.push(i);
        }

        while (!st.empty()) {
            int i = st.top();
            ans[i] = prices[i];
            st.pop();
        }
        return ans;
    }

    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st;
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int pre = st.top();
                ans[pre] = i - pre;
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};